package violentRecursion;

import org.junit.Test;

/**
 * @author kunkun
 * @className LeetCode_152
 * @Description 乘积最大子数组
 * @date 2025/3/14 13:54
 */
public class LeetCode_152 {

    public int maxProduct(int[] nums) {
        return solution_1(nums);
    }

    @Test
    public void test(){
        System.out.println(maxProduct(new int[]{2, 3, -2, 4}));
    }

    /**
    * @Description: 方法1：动态规划
    * @Author: kunkun
    * @Date:  2025/3/17 14:47
    * @Parameters:
    * @Return
    * @Throws
    */
    public int solution_1(int[] nums){
        // 1. 排除特殊情况
        if (nums.length==1){
            return nums[0];
        }
        // 2. 递归计算max和min
        int[] max=new int[nums.length]; //定义以第i位置结尾的最大值
        int[] min=new int[nums.length]; //定义以第i位置结尾的最小值
        max[0] = nums[0];
        min[0] = nums[0];

        // 3. 递归计算max
        for (int i = 1; i < nums.length; i++) {
            int tempMaxBefore = max[i-1],tempMinBefore = min[i-1];
            max[i]= findNum(nums[i]*tempMaxBefore,nums[i]*tempMinBefore,nums[i],true);
            min[i]= findNum(nums[i]*tempMaxBefore,nums[i]*tempMinBefore,nums[i],false);
        }
        // 4. 返回最大值
        int result = max[0];
        for (int i = 1; i < max.length; i++) {
            if (max[i]>result){
                result = max[i];
            }
        }
        return result;
    }


    public int findNum(int a,int b,int c,Boolean isMax){
        if (isMax){
            return Math.max(Math.max(a,b),c);
        }else {
            return Math.min(Math.min(a,b),c);
        }
    }


}
